\documentclass[11pt,a4paper,serbianc,oneside]{book}
\usepackage[utf8x]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{textcomp}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{ucs}
\usepackage{listings}
\usepackage[serbianc]{babel}
\usepackage{pdfsync}
\usepackage[left=2.5cm,right=2.5cm,top=2.5cm,bottom=2.5cm]{geometry}
\usepackage[ruled,noline,algochapter]{algorithm2e}



% Komanda za horizontal ruler
\newcommand{\HRule}{\rule{\linewidth}{0.5mm}}

%
% Definicija fiksiranih reci
%
\addto\captionsserbian{%
 \def\prefacename{Предговор}%
 \def\refname{Списак литературе}%
 \def\abstractname{Сажетак}%
 \def\bibname{Литература}%
 \def\chaptername{Глава}%
 \def\appendixname{Додатак}%
 \def\contentsname{Садржај}%
 \def\listfigurename{Списак слика}%
 \def\listtablename{Списак табела}%
 \def\indexname{Регистар}%
 \def\figurename{Слика}%
 \def\tablename{Табела}%
 \def\partname{Део}%
 \def\enclname{Прилози}%
 \def\ccname{Копије}%
 \def\headtoname{Прима}%
 \def\pagename{Страна}%
 \def\seename{Види}%
 \def\alsoname{Види такође}%
 \def\proofname{Доказ}%
 \def\glossaryname{Речник непознатих речи}
 \def\contentsname{Садржај}%
 }%

%
% Podesavanja paketa za listinge
%

\renewcommand{\algorithmcfname}{Алгоритам}


\renewcommand\lstlistingname{Листинг}
\lstset {
	basicstyle=\footnotesize\ttfamily,
	numbers=left,
	numberstyle=\tiny,
	%stepnumber=2,
	numbersep=5pt,
	tabsize=2,
	extendedchars=true,
	breaklines=true,
	keywordstyle=\color{blue},
	frame=b,
	stringstyle=\color{gray}\ttfamily,
	showspaces=false,
	showtabs=false,
	xleftmargin=17pt,
	framexleftmargin=14pt,
	framexrightmargin=3pt,
	framexbottommargin=4pt,
	framextopmargin=0pt,
	%backgroundcolor=\color{lightgray},
	showstringspaces=false
}

\lstloadlanguages {
	% Check Documentation for further languages ...
	%[Visual]Basic
	%Pascal
	%C
	%C++
	Java,
	XML,
	Bash,
	Python
}

%
% Podesavanje okvira listinga
%
\usepackage{color}
\usepackage{colortbl}
\usepackage{xcolor}
\usepackage{caption}
\usepackage{float}
\floatstyle{plaintop}
\restylefloat{table}
\DeclareCaptionFont{white}{\color{white}}
\DeclareCaptionFormat{listing}{\colorbox[cmyk]{0.43, 0.35, 0.35,0.01}{\parbox{\textwidth}{\hspace{12pt}#1#2#3}}}
\captionsetup[lstlisting]{format=listing,labelfont=white,textfont=white, singlelinecheck=false, margin=0pt, font={bf,footnotesize} }

%
% Pocetak dokumenta
%
\begin{document}

\input{naslovna-si.tex}


\tableofcontents
\newpage


\chapter*{Апстракт}

Циљ овог рада је опис истраживања глаткости молекулских структурних дескриптора у хемијској теорији графова. Ради лакшег разумевања садржаја рада, потребно је да читаоци имају предзнање из матемаичке теорије графова.


У првом поглављу је дат увод у употребу графова у хемији, дефинисани су структурни дескриптори и објашњена је њихова улога у хемији. 

Друго поглавље представља поставку проблема и алгоритам високог нивоа за добијање резултата. Објашњен је и алгоритам за линеарну проверу изоморфизма стабала.



\newpage
\chapter{Увод у хемијску теорију графова}
\section{Графови у хемији}
  
Структурне формуле органских једињења добијају се тако што се сваки појединачни атом прикаже својим симболом ($C$ за угљеник, $H$ за водоник, $O$ за кисеоник,...). Ако између два атома постоји ковалентна хемијска веза, онда се између одговарајућих симбола повлачи црта (или две, односно, три црте ако се ради о двогубој, односно трогубој вези). Дакле, структурна формула молекула (односно хемијских јединњења) показује који парови атома су хемијски везани. Број хемијских веза које се завршавају у једном атому назива се валенца тог атома. 

Граф који одговара структурној формули назива се \textbf{молекулски граф} одговарајућег молекула. Постоје две врсте молекулских графова:плерограм и кенограм.

\textbf{Плерограм} се конструише тако што се сваки атом приказује чвором, а два чвора су суседна ако су одговарајући атоми хемијски повезани. Слика \ref{fig:plero} показује један плерограм и структурну формулу хемијског једњења  
представљеног тим плерограмом.

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=150mm]{images/plerogram.png}
\end{center}
\caption{Плерограм}
\label{fig:plero}
\end{figure}

\textbf{Кенограм} се конструише тако што се чворовима приказују сви атоми осим водоникових. На тај начин кенограм репрезентује само (угљенични) скелет органског молекула. Слика \ref{fig:keno} показује један кенограм и структурну формулу хемијског једнњења  
представљеног тим кенограмом.

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=150mm]{images/kenogram.png}
\end{center}
\caption{Кенограм}
\label{fig:keno}
\end{figure}


Истрживања у савременој хемијској теорији графова готово искључиво се врше на кенограмима. У литератури се, зато, 
често, говори о молекулским графовима, подразумевајући при томе кенограме. То ћемо надаље чинити и у овом раду.


Стабла служе за графовску репрезентацију ацикличних молекула, нарочито алкана. У том случају граф одговара угљеничном скелету, а његови чворови репрезентују атоме угљеника. Јасно је, стога, да стабла којима приказујемо алкане не могу имати чворове чији је степен већи од четири.

Повезани граф без циклова, који не садржи чворове степена већег од 4, назива се \textbf{хемијско стабло}. 

Хемијска стабла су веома често објекти истраживања у хемијској теорији графова. Алкани, са тачке гледишта структурне хемије, су најједноставнија органска једињења. Садрже само две врсте хемијских веза: једноструке ковалентне везе угљеник-угљеник и ковалентне везе угљеник-водоник. Због тога је опис њихове електронске структуре релативно једноставан. Молекули алкана су скоро неполарни, што омогућава да се њихово физичко-хемијско понашање описује једноставним математичким моделима.

Хемијска стабла, која представљају математички модел алкана, спадају у графове са најједноставнијим особинама. Многи математички проблеми који се у случају свих (молекулских) графова тешко или никако не могу решити, имају допадљива решења у случају (хемијских) стабала. С друге стране, особине хемијских стабала нису уопште тривијалне и њихова истраживања доводе до резултата који су вредни и са математичке тачке гледишта. 

Због свих наведених разлога, математички модели који имају за циљ да повежу молекулску структуру са физичким, хемијским, фармаколошким и другим особинама хемијских једињења, по правилу се прво тестирају на алканима, уз примену хемијских стабала. То је поготово случај са структурним дескрипторима заснованим на графовима.



У теоријској хемији говори се о алтернативним и неалтернативним конјугованим угљоводоницима. За конјуговани угљоводоник кажемо да је \textbf{алтернативан} ако му је молекулски граф бипартитан. У супротном угљоводоник је \textbf{неалтернативан}.




Молекулски графови полицикличних једнињења често садрже велики број циклова. Препознавање циклова у молекулским графовима, те одређивање њиховог броја је тежак задатак. Тај, наизглед једноставан проблем, није, до данашњег дана, решен нa ефикасан начин.

Оно што се у хемији конципира као "број прстенова" у једињењу је, у ствари, цикломатични број из теорје графова. У квантној хемији је веома рано установљено да $\pi$-електорнске особине конјугованих угљоводоника веома зависе од врсте циклова садржаних у молекулском графу.



\section{Молекулски структурни дескриптори}

\subsection{Општа разматрања}


Молекулски структурни дескриптори засновани на молекулском графу често се називају \textbf{тополошки индекси} \cite{gutman}. 

У вези са молекулским тополшким индексима морамо увек имати на уму следећи општи проблем. Молекулска структура је ненумерички појам, па се често не може у потпуности описати бројевима. С друге стране, у хемији, врше се мерења и сви мерни резултати се изражавају бројем. На тај начин, једној одређеној супстанци се могу придружити разни молекулски подаци, који одговарају њеним физичко-хемијским особинама. 

Једна од парадигми хемије је да су физичко-хемијске особине једињења условљена структуром молекула од којих се то једињење састоји. Трагање за везама између молекулске структуре (ненумеричког појма) и физичко-хемијских особина једињења (које су изражене бројем) јесте једно од основних циљева хемије као науке. 

Нека је $I=I(G)$ математички ентитет (број, матрица, полином, вектор, група,...) које се на неки начин придружује графу $G$. Ако је задовољен услов да за свака два изоморфна графа $G_1$ и $G_2$ важи $I(G_1)=I(G_2)$ онда се каже да је $I$ \textbf{инваријанта графа} или да је $I$ графовска инваријанта.

Треба обратити пажњу да из услова $I(G_1)=I(G_2)$, не следи да су графови $G_1$ и $G2$ изоморфни. Када би то био случај, онда би инвријанта $I$ потпуно одређивала структуру графа. Такава инваријанта до данас није откривена.

Графовске инваријанте са којима смо се до сада упознали су, између осталог: број чворова, борј грана, цикломатични број, број савршених спаривања, полином спаривања, карактеристични полином, спектар графа. Матрица суседства није инваријанта графа, јер њен конкретни облик зависи од нумерације чворова. Из истог разлога ни матрица растојања није инваријанта графа. 

Лако је вдиети да је број могућих графовских инваријанти бесконачно велик. Због тога нас, како у теорији графова тако и у хемијској теорији графова, занимају само неке погодно одабране инваријанте.

Показало се да се неке графовске инваријанте могу довести у везу са физичко-хемијским особинама молекула, и такве инваријанте се онда проучавају у хемијској теорији графова.  У почетку, негде до краја седамдестих година прошлог века, у хемијској литератури је био разматран сасвим мали број таквих инваријанти. Тада, међутим, број ових тополошких индекса починње нагло да расте, тако да данас има неколико стотина озбиљно разматраних, и много хиљада "предложених" тополошких индекса.

Да би се ова појава некако обуздала предложени су критеријуми за уврштавање једне графовске инваријанте међу легитимне молекулске структурне дескрипторе.

% Стави референцу на Балабана
Балабан је поставио следеће услове:

\begin{enumerate}
\item Добра корелација са физичко-хемијским особинама.
\item Низак степен дегенрације или потпуно одсуство дегенерације.
\item Лакоћа израчунавања.
\item Пораст са порастом разгранатости молекулског скелета.
\item Могућност да се модификује тако да буде применљив код незасићених једињења као и код једињења која садрже хетероатоме.
\end{enumerate}

Под \textbf{дегенерацијом} једног структурног дескриптора подразумева се појава да дескиптор има исту вредност за различите (неизоморфне) графове, Ако је $\zeta$  неки скуп молекулских графова, а $\iota$ неких скуп свих различитих вредности које инваријанта $I$ поприма у скупу $\zeta$, онда се степен дегенерације у скупу $\zeta$ може дефинисати као:

\begin{equation}
\delta = \frac{|\zeta| - |\iota|}{|\zeta| - 1},
\end{equation}

при чему $|\zeta|$ и $|\iota|$ означавају број елемената одговарајућих скупова. Ако сви графови из скупа $\zeta$ имају различите вредности за $I$, онда је $\delta = 0$, а ако сви графови имају исту вредност за $I$ онда је $\delta = 1$.


Рандић је формулисао следеће критеријуме:

\begin{enumerate}
\item Могућност непосредне структурне интерпретације.
\item Корелација са макар једном физичко-хемијском особином.
\item Могућност разликовања изомера.
\item Локална дефинисаност (то јест, дефиниција на основу структурних детаља везаних за чвор и/или грану и њихову непосредну околину).
\item Могућност да се уведе низ аналогних дескриптора "вишег реда".
\item Линеарна независност.
\item Једноставност.
\item Да није заснован на физичко-хемијским особинама.
\item Да није, на тривијлан начин, повезан са другим структурним дескрипторима .
\item Да се може ефикасно израчунати.
\item Да је дефинисан на основу лако разумљивих структурних концепата.
\item Да има коректну зависност од величине молекула.
\item Да се постепено мења при малим променама у молекулској структури.
\end{enumerate}


\subsection{Винеров индекс}

Нека је $G$ повезани граф. Збир растојања између свих парова чворова графа $G$ назива се \textbf{Винеров(Wiener)} индекс тога графа и обележава се са $W=W(G)$. 

Винеров индекс се сматра најстаријим молекулским структурним дескритпором, а чланак у ком је објашњен почетком примене структурних дескриптора у хемији.

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=100mm]{images/34dmth.png}
\end{center}
\caption{3,4-диметилхексан}
\label{fig:34dmth}
\end{figure}


Помоћу математичких формула Винеров индкес се може задати на следеће међусобно еквивалентне начине:

\begin{equation}
W(G) = \sum_{r \le s} d(v_r, v_s) = \frac{1}{2} \sum_{r=1}^n \sum_{s=1}^n d(v_r, v_s) = \sum_{\{v_r, v_s\}\subseteq V(G) } d(v_r, v_s) 
\end{equation}

Ако са $D_{i,j}$ означимо $(i,j)$-ти елемент матрице растојања, онда је:

\begin{equation}
W(G)=\sum_{i<j} D_{i,j} = \frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n D_{i,j}
\end{equation}

Нека је $G$ молекулски граф 3,4-диметилхексана, приказаног на Слици \ref{fig:34dmth}, и нека су му чворови означени као на слици. Тада важи да је $W(G)=68$, што се може закључити ако би се сабрали елементи који леже изнад главне дијагонале  матрице растојања

\begin{equation}
D(G)=
\left[ \begin{matrix} 
0 &1 &2 &3 &4 &5 &3 &4 \\ 
1 &0 &1 &2 &3 &4 &2 &3 \\ 
2 &1 &0 &1 &2 &3 &1 &2 \\ 
4 &3 &2 &1 &0 &1 &3 &2 \\ 
5 &4 &3 &2 &1 &0 &4 &3 \\ 
3 &2 &1 &2 &3 &4 &0 &3 \\ 
4 &3 &2 &1 &2 &3 &3 &0 \\ 
\end{matrix} \right]
\nonumber
\end{equation}

Нека је $d(G,k)$, број парова чворова графа $G$ чије је међусобно растојање једнако $k$. Јасно је да се међу елементима матрице суседства број $k$ појављује тачно $d(G,k)$ пута. 

Непосредно из дефиниције Винеровог индекса следи да је:

\begin{equation}
W(G) = 1 \times d(G,1) + 2 \times d(G,2) + 3 \times d(G,3) + ...
\end{equation}

то јест:

\begin{equation}
W(G) = \sum_{k \geq 1} k d (G,k)
\end{equation}

Претходни образац је интересантан јер се у њему не захтева да граф $G$ буде повезан. Тиме је омогућено дефинисање Винеровог индекса и за неповезане графове.

Тешко је набројати које су све хемијске, физичко-хемијске и фармаколошке особине органиских (а у новије време и неорганских) једињења биле доведене у везу са Винеровим индексом. У свом првом раду Винер је показао да се помоћу $W$ могу предвиђати тачке кључања алкана. У каснијим радовима показао је да се исто може учинити са топлотом изомеризације и топлотом испаравања, напоном паре, површинским напоном и индексом преламања. Такође, Винер је указао и на везу његовог индекса и међумолекулских сила, што је у пуној мери разрађено тек касније. 

Касније, у бројним радовима, показана је и применљивост Винеровог индекса за предвиђање густине, моларне запремине, индекса рефракције, вискозности, разних термохемијских величина (топлоте настајања, топлоте атомизације), критичне температуре и критичног притиска, брзине простирања звука, хроматографских ретенционих времена, како ацикличних, тако и цикличних, како алифатичних тако и ароматичних једињења, како угљоводоника тако и једињења са функционалним групама и хетероатомима \cite{gutman}.

Од мање стандардних примена могу се поменути одређивање просечне конформације алкана са дугачким угљениковим ланцима, разликовање изомера фулерена, опис механизма електроредукције, опис кристалних дефеката, а у најновије време предиђање константи равнотеже комплексних једињења. Објављене су и многе фармаколошке примене Винеровог индекса.


\subsection{Хасојин индекс}
Почетком седамдесетих година прошлог века Хасоја (Hosoya) је увидео значај једне комбинаторне особине органских једињења, о којој до тада нико међу хемичарима није размишљао. Иако се већ читав век знало да у органским молекулима постоје хемијске везе, и да између тих веза, нарочито између суседних, постоје некакве интеракције, тек је Хасоја почео да истражује односе који владају међу несуседним хемијским везама.


Ако се молекул прикаже својим уобичајеним молекулским графом $G$, онда је број начина на који се у том молекулу може изабрати $k$ међусобно несуседних угљеник-угљеник веза једнак броју $m(G,k)$ избора $k$ независних грана, односно $k$-спаривањаа у графу $G$. Са бројевима $m(G,k)$ смо већ упознати.


Укупан број спаривања у графу $G$, odnosno $\sum_{k \geq 0}m(G,k)$, назива се \textbf{Хасојин} индекс графа, и означава се са $Z=Z(G)$.


Треба имати у виду да сабирање почиње од $k=0$ и да је за сваки граф $m(G,0)=1$. Због тога увек важи да је $Z(G) \geq 1$.

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=50mm]{images/stiren.png}
\end{center}
\caption{Стирен}
\label{fig:stiren}
\end{figure}


Из графа на Слици \ref{fig:stiren} видимо да је за молекулски граф стирена (или, што је исто, за молекулски граф етил-циклохексана) одговарајући Хасојин индекс има вредност 44, јер је $m(G,0)=1,m(G,1)=8,m(G,2)=19,m(G,3)=14,m(G,4)=2,m(G,k)=0$ за $k>4$.

За разлику од Винеровог индекса, готово све хемијске примене Хасојиног индкеса разрадио је Хасоја са својим сарадницима. У низи чланака који обухватају период од око 30 година, показано је да се поред тачке кључања алкана, Хасојиним индексом могу моделовати разни термодинамички параметри засићених угљоводоника, посебно ентропија, што се могло и теоријски доказати. Установљена је и веза између Хасојиног индекса и статичко механичког описа молекула \cite{gutman}. 


У другом низу радова $Z$ је примењен у теорији конјуговаих $\pi$-електронских система: на укупну $\pi$-електронску енергију, ред везе и расподелу наелектрисања. 

\subsection{Индекс повезаности}

Индекс повезаности увео је Рандић, па се он помиње и као Рандићев индекс повезаности. Као што је раније поменуто, $\delta_v$ означава степен чвора $v$.


\textbf{Индекс повезаности} графа $G$ је 

\begin{equation}
\label{eq:povezanost}
\chi = \chi(G)=\sum_{u,v} \frac{1}{\sqrt[]{\delta_u, \delta_v}}
\end{equation}
при чему се сабирање врши преко свих парова суседних чворова графа $G$.

Нема сумње да је, са тачке гледишта примена у хемији и фармакологији, индекс $\chi$ највише и најчешће примењивани молекулски структурни дескриптор. Један од разлога његове велике популарности је, свакако, што се $\chi$ добро корелира са разним молекулским особинама. Други разлог је што се $\chi$ лако израчунава и што за његово израчунавање није потребна иоле већа теоријска припрема. Трећи разлог је, што за разлику од Винеровог, Хасојиног и још понеког индекса, $\chi$ није цео него децималан број. Још један разлог за успех индекса повезаности је што се он релативно лако модификује за хетероатоме, те што постоје његове природне генерализације. 

Израз наведен у Обрасцу \ref{eq:povezanost} може се схватити као "индекс повезаности првог реда", $^1\chi$. Тада би индекс ``повезаности другог реда`` био:

\begin{equation}
^2\chi = ^2\chi(G) = \sum_{u,v,w}  \frac{1}{\sqrt[]{\delta_u, \delta_v, \delta_w}},
\end{equation}

где сабирање обухвата све путеве $P_3$ који се као подграфови садрже у графу $G$, при чему $u,v,w$ означава чворове који, тим редом, припадају путу $P_3$. На аналоган начин се уводе индекси повезаности трећег реда (сабирање преко свих подграфова $P_4$), четвртог реда (сабирање преко свих подграфова $P_5$), и вишег реда. Индекс повезаности нултог реда се тада природно одређује као:

\begin{equation}
^0 \chi(G)= \sum_v \frac{1}{\sqrt{\delta_v}}\ ,
\end{equation}
где се сабирање врши преко свих чворова графа $G$.

Најопштија генерализација израза \eqref{eq:povezanost} је следећа:
\begin{equation}
^{(H)} \chi (G)= \sum_H \frac{1}{\sqrt{\delta(H)}},
\end{equation}
где је $H$ неки подграф графа $G$, $\delta(H)$ је производ степена свих оних чворова графа $G$, који припадају подграфу $H$, а сабирање иде преко свих подграфова графа $G$, који су изоморфни графу $H$.

У случају да се атоми у посматраном молекулу разликују од угљениковог, модификације индекса повезаности (и његових управо описаних поопштења) врши се тако што се уместо степена чвора употребљава неки сложенији израз, коjи зависи од редног броја, електронегативности исл. 

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=100mm]{images/cicor.png}
\end{center}
\caption{Kорелација између тачке кључања и индекса повезаности}
\label{fig:cicor}
\end{figure}

Велика већина савремених примена индекса повезаности односи се на поопштења и модификације оригиналне формуле. Помоћу индекса повезаности моделоване су разноразне физичко-хемијске величине као што су енталпија кристалне решетке металних халида, тачка кључања алкохола и амина, брзина реакције дехидрогеновања халогено супституисаних угљоводоника, и анестетичко деловање хлоро-флуоро-супституисаних метана и етана. Такође, индекс карактерише обилна фармаколошка примена \cite{gutman}. 


На Слици \ref{fig:cicor} се може видети корелација између тачке кључања C2-C7 алкана и индекса повезаности $\chi$.





\subsection{Математичка истраживања индекса повезаности}

Индекс повезаности дефинисан је на тако једноставан начин да скоро и не постоји потреба да се испитује његова зависност од молекулске структуре. Због тога математички хемичари на њега дуго времена скоро и да нису обраћали пажњу. 

Промена је настала крајем прошлог века, када се мађарско-амерички математичар Ердеш заинтересовао за $\chi$. Он је доказао да међу свим повезаним графовима са $n$ чворова звезда $S_n$ има најмању вредност за $\chi$. Значај рада је у томе што је њиме показано да у вези са индексом повезаности постоје нетривијални, тешки и интересантни математички проблеми. До сада је у вези са индексом повезаности графова и молекулских графова добијено само неколико резултата. 

Ако је $G$ повезани граф са $n$ чворова онда је 
\begin{equation}
\sqrt{n-1} \leq \chi(G) \leq \frac{n}{2}.
\end{equation}

Најмању вредност за $\chi$ има звезда $S_n$, за коју је $\chi(S_n) \leq \frac{n}{2}$. Највећу вредност за $\chi$ имају сви графови чије су све компоненте регуларни графови. 

Ако је $T$ стабло са $n$ чворова, различито од звезде  $S_n$ и пута $P_n$, онда је:

\begin{equation}
\chi(S_n) < \chi (T) < \chi(P_n).
\label{eq:pz}
\end{equation}

Као што је већ речено $\chi(S_n) < \sqrt{n-1}$. Лако се показује да је $\chi(P_n) = \sqrt{2} + (n-3)/2$ за свако $n \geq 3$.

Једначина \ref{eq:pz} показује да је $P_n$ хемијско стабло са највећим индексом повезаности. Хемијска стабла са најамњим индексом повезаности су позната, али она нису јединствена. Постоји велики број стабала са истим, минималним индексом повезаности. Сва она су веома разграната.


\chapter{Струткурна осетљивост тополошких индекса}

\section{Глаткост хемијског индекса}

\subsection{Увод}


Као што је већ речено, тополошки индекс је нумеричка вредност повезана са хемијским саставом, која служи за одређивање корелације хемијске структуре са разним физичким особинама, хемијским реакцијама и биолошким активностима. Индекси који су базирани на молекулском графу су се показали као врло корисни, како у разним хемијским дисциплинама, тако и у многим другим областима. Данас постоји велики број таквих индекса. Код многих од њих, хемијска применљивост никад није била тестирана.

Познато је да је Рандић, између осталих, предложио критеријумe за уврштавање једног тополошког индекса међу легитимне молекулске структурне дескрипторе. Један од тих критеријума каже да је тополошки индекс валидан структурни дескриптор уколико се за малу промену молекуларне структуре вредност индекса мења постепено. Ова особина се назива \textbf{глаткост} хемијског индекса који се испитује. 

Иако потпуно разумљива и интуитивно прихватљива особина, глаткост хемијског индекса до данас никад није била испитивана. У овом раду је вршено истраживање које треба да попуни ту празнину.

\subsection{Квантификација глаткости}

Како би могли да квантификујемо глаткост тополошког индекса (и самим тим омогућимо упоређивање са другим индексима), уводимо две мере: струткурна осетљивост и максимални отклон \cite{boris}. Као предуслов за дефинисање ових појмова, треба објаснити процес генерисања скупа структурно сличних графова неком графу $G$.  

Нека је $G$ неки граф. Нека су $v_r, v_s$ и $v_t$ неки чворови графа $G$, такви да $(v_r, v_s)\in E(G)$ и $(v_r, v_t) \not\in E(G)$. Са $G'$ обележавамо граф који се добије уклањањем $(v_r, v_s)$ из $E(G)$ и додавањем $(v_r, v_t)$ у $E(G)$. За граф $G'$ кажемо да је настао минималном променом у графу $G$ (једна грана је замењена новом). 

Нека је $S(G)$ скуп графова. Скуп $S(G)$ правимо тако што прво претходном трансфромацијом $G \rightarrow G'$ генеришемо све могуће графове $G'$. Да би генерисани граф $G'$ додали у $S(G)$, он мора да задовољава следеће услове:
\begin{itemize}
\item $G'$ је повезан граф,
\item $G'$ није изоморфан са $G$,
\item $G'$ није изоморфан ни са једним елементом из $S(G)$.
\end{itemize}

Овако генерисан скуп $S(G)$ се може назвати \textbf{GED(G)=1 скупом}, тј. скупом графова чија је GED (\textit{graph edit distance}) вредност у односу на $G$ једнака 1. Верујемо да се овај скуп састоји од графова стуктурно најсличнијих графу $G$. Самим тим, разлика тополошког индекса графа $G$ и графа из $S(G)$ може да репрезентује осетљивост тополошког индекса на малу промену у графу. 


Сада можемо дефинсати следећи појам:


\textbf{Структурна осетљивост} индекса $TI$ у односу на граф $G$ је вредност:

\begin{equation}
SS(G) = \sigma(TI) = \sqrt{ \frac{1}{|S(G)|} \sum_{G' \in S(G)} (TI(G') - \mu(TI))^2 }
\end{equation}

где је: $|S(G)|$ број елемената скупа $S(G)$, $TI(G')$ вредност тополошког индекса који испитујемо за граф $G'$, а $\mu(TI)$  аритметичка средина вредности тополошких индекса свих графова у $S(G)$. Закључује се да $SS(G)$ представља стандардну девијацију у скупу вредности тополошких индекса за графове из $S(G)$.


Ако $SS(G)$ има високу вредност, онда претпостављамо да тополошки индекс $TI$ има мали или никакав значај. Ако, међутим, $SS(G)$ има ниску вредност, то и даље није гаранција да је индекс "валидан", јер вредност тополшких индекса може да буде хаотичан скуп. Да би ово проверили дефинишемо следећи појам:

\textbf{Максимални отклон} тополошког индекса $TI$ у односу на граф $G$ је вредност:

\begin{equation}
 Abr(TI, G) = \max_{G' \in S(G)} \bigg\vert TI(G') - TI(G)\bigg\vert .
\end{equation}

Оно што називамо максимални отклон, показује колико мала структурна промена у графу изазива велику промену у вредности испитиваног тополошког индекса. 

Са практичне тачке гледишта, најбоље је да су вредности за структурну осетљивост и максимални отклон довољно мале.


\subsection{Испитивани индекси}
У претходном одељку смо дефинисали начин на који је могуће квантификовати глаткост тополошких индекса. У овом раду фокусираћемо се на тополошке индексе засноване на степенима чворова графа, дакле индексе у облику:

\begin{equation}
TI(G) = \sum_{(u,v) \in E(G)} F(d_u, d_v)
\end{equation}
где је $E(G)$ скуп грана графа $G$, $u$ i $v$ чворови у графу $G$, $d_u$  и $d_v$ степени чворова $u$ и $v$, а $F$ функција(одређена тополошким индексом) над степенима чворова.


Познато је да на нумеричку вредност индекса заснованог на степенима чворова, највише утичу број чворова и број грана графа. Самим тим, логично је упоређивати разноразне вредности $TI$ за графове који имају исти број чворова и грана. У овом раду, разматраће се класе стабала са истим бројем чворова.

У Табели \ref{table:indices} дат је приказ индекса који ће бити испитивани.
\vspace{10mm}
\begin{table}[H]
\caption{Испитивани индекси}
\centering
 \begin{tabular}{l r}
Име индекса & Матеметичка дефиниција\\
\hline
 & \\
\textit{Randić}‎ & $R=\sum_{u,v \in E(G)} \frac{1}{\sqrt{d_u d_v}}$ \\
 & \\
\textit{First Zagreb} & $M1=\sum_{u,v \in E(G)} (d_u + d_v)$ \\
 & \\
\textit{Second Zagreb} & $M2=\sum_{u,v \in E(G)}(d_u d_v)$ \\
 & \\
\textit{Atom-bond connectivity} & $ABC=\sum_{u,v \in E(G)} \sqrt{\frac{d_u + d_v -2}{d_u d_v}}$ \\
 & \\
\textit{Sum-connectivity} & $SCI=\sum_{u,v \in E(G)}\frac{1}{\sqrt{d_u + d_v}}$ \\
 & \\
\textit{First geometric-arithmetic} & $GA1=\sum_{u,v \in E(G)}\frac{2\sqrt{d_u d_v}}{d_u + d_v}$ \\
 & \\
\textit{Augmented Zagreb} & $AZI=\sum_{u,v \in E(G)} \bigg ( \frac{d_ud_v}{d_u + d_v - 2} \bigg)^3$ \\
 & \\
\textit{Harmonic} & $HI=\sum_{u,v \in E(G)}\frac{2}{d_u + d_v}$ \\
\label{table:indices}
\end{tabular}

\end{table}

\section{Рачунарска имплементација израчунавања глаткости хемијског индекса}

\subsection{Алгоритам за израчунавање}
На основу дефиниција за израчунавање лако се закључује који кораци су потребни за добијање вредности $SS$ и $Abr$ за неки тополошки индекс. У сврху решавања проблема написан је софтвер који ће детаљније бити разматран касније у овом раду. Како смо већ описали поступак добијања $SS$ и $Abr$, Алгоритам \ref{alg:ssabbr}, описан псеудокодом, се намеће као валидно решење које треба софтверски имплементирати.
 
У  алгоритму, као улаз имамо променљиве $T(n), EI$ и $F$. Под $T(n)$ подразумевамо скуп свих неизоморфних стабала са $n$ чворова. $EI$ означава скуп имена индекса које испитујемо, a $F$ низ математичких функција које карактеришу одговарајући индекс. Резултат представља просечну вредност за $SS$ и $Abr$ у класи стабала задатој на улазу.

\vspace{1mm}
\begin{algorithm}[H]
 \KwData{$T(n), EI, F$}
 \For{$T\in T(n)$}{
 $S(T)=\emptyset$\;
  \For{$node \in V(T)$}{
  	\For{$ neighbor \in \{neighbor: (node, neigbor) \in E(T)\}$}{
  		\For{$nonneighbor \in \{noneighbor: (node, nonneigbor) \not\in E(T)\}$}{
  			$T' \leftarrow T$\;
  			 $ E(T') \leftarrow E(T) - (node, neigbor) + (node, noneighbor)$\;
  			\If{($T'$ is connected) \textbf{and} ($T' \not\cong T$) \textbf{and} $(\neg\exists T_s \in S(T) : T'\cong T_s)$ }{
				$S(T) \leftarrow S(T) + T'$  			
  			}
  		}
  	}
  }

  \For{$index$ in $EI$}{
    	 $TI_T = \sum_{(d_u, d_v) \in E(T)} F[index](d_u, d_v)$ \;
  	 \vspace{1mm}
  	 $TIvalues = \{\sum_{(d_u, d_v) \in E(S)} F[index](d_u, d_v): S \in S(T)\}$\;
  	 \vspace{1mm}
  	 $SS[index] [T] = \sigma (TIvalues)$\;
  	 $Abr[index] [T] = \max_{\; TI_v \;\in \; TIvalues} \bigg\vert TI_v - TI_T\bigg\vert$\;
  }
 }
 \For{$index$ in $EI$}{
  	 $AverageSS = \frac{\sum_{T\in T(n)} SS[index][T] }{|T(n)|} $\;
  	 $AverageAbr = \frac{\sum_{T\in T(n)} Abr[index][T] }{|T(n)|} $\;
  	 \vspace{1mm}
  	 \textbf{print} \textit{index, AveragaeSS, AverageAbr}
  } 

 
 
 \caption{Израчунавање структурне осетљивости и максималног отклона} 
 \label{alg:ssabbr}
\end{algorithm}

\subsection{Комплексност алгоритма за израчунавање}

Иако на први поглед алгоритам изгледа прилично једноставан за имплементирање, постоје ствари на које треба обратити пажњу. 

У Tабели \ref{tab:treenum} је дат преглед броја нeизоморфних стабала које алгоритам обрађује у зависности од броја чворова. Уочава се да број стабала интензивно расте са порастом броја чворова. 

Сада ћемо покушати приближно да одредимо комплексност описаног алгоритма за израчунавање глаткости тополошког индекса. Анализираћемо део који се односи на генерисање $GED=1(G)$ скупа. За остатак алгоритма вредности су очигледне. 

Пошто је познато да провера комплексности алгоритма не захтева строго прецизно израчунавање броја потрeбних операција, увешћемо нека уопштења. 

Обратимо пажњу на две $for$ петље које се извршавају при итерацији суседних и несуседних чворова неком одређеном чвору. Број ових итерација дакле представља број (не)суседа неког чвора, различит је у сваком пролазу и зависи од структуре стабла које се тренутно испитује. Није потребно знати тачан број тих итерација како бисмо одредили комплексност алгоритма. Ради упрошћења проблема, претпоставићемо да је број тих итерација сталан и да његова вредност одговара просечној вредности тачног броја итерација. Број тих итерација обележавамо $C_1n$ и $C_2n$ где су $C_1$ и $C_2$ неке константе, а $n$ број чворова стабла. Уочавамо да је $C_1 < 1$, $C_2 < 1$ . Оно што је битно уочити, јесте да број тих итерација зависи од $n$. Заиста, са повећањем броја чворова, повећава се број могућих (не)суседа неком чвору.

\begin{table}[h]
\centering
\caption{Број неизоморфних стабала}
\begin{tabular}{l r}
Број чворова & Број неизоморфних стабала\\
\hline
&\\
1& 1 \\
2& 1\\
3 &1\\
4 &2\\
5 &3\\
6 &6\\
7 &11\\
8 &23\\
9 &47\\
10 &106\\
11 &235\\
12 &551\\
13 &1,301\\
14 &3,159\\
15 &7,741\\
16 &19,320\\
17 &48,629\\
18 &123,867\\
19 &317,955\\
20 &823,065\\
\end{tabular}

\label{tab:treenum}
\end{table}

Сада ћемо анализирати део који се односи на додавање генерисаног стабла постојећем скупу већ изгенерисаних, неизоморфних стабала. Провера повезаности је проблем који има линерану комплексност и познато је да њему одговара $C_3n$ операција. Обратимо пажњу на део кода за проверу изоморфности. Овај део кода биће извршен само у случају да је изгенерисан граф повезан. Уопштавања ради, процентуални број изгенерисаних повезаних графова можемо сматрати сталним и обележићемо га са $C_4, C_4<1$.  Провере изморофности захтевају $C_5n$ операција. Oво на први поглед делује као лош избор, пошто је познато да алгоритам за израчунавање изоморфизма графова, у најгорем случају има комплесност $O(n!)$. Међутим, коришћењем посебних, оригинално уведених техника уз нека одређена ограничења, ово је изводљиво (касније ћемо објаснити на који начин).

Посматрајући алгоритам, долазимо до закључка да је број операција потребан за извршавање алгоритма:

\begin{equation}
|T_n|\cdot (n \cdot C_1n \cdot C_2n \cdot (C_3n + C_4C_5n ) +C_6n)+ C_7n  = C_0n^4 + C_8n,
\label{eq:numop}
\end{equation}
где је $|T_n|$ број стабала, $n$ број чворова стабла, $C_1n$ просечан број суседних чвоврова,  $ C_2n$ просечан број несуседних чворова, $C_3n$ број операција за проверу повезаности, $C_4$ процентуални број изгенерисаних повезаних стабала, $C_5n$ број операција за проверу изоморфности, $C_6n$ број операција за рачунање  $SS$ и $Abr$, и $C_7n$ број операција за рачунање просечне вредности $SS$ и $Abr$.

На основу  Једначине \ref{eq:numop}, уочавамо да алгоритам има комплексност $O(n^4)$. 


\section{Провера изоморфизма у линеарном времену}

\subsection{Увод}
Провера изоморфизма графова се показала као изазован проблем у току истраживања. Конреткно се мисли на проверу да ли је неки граф изоморфан са било којим елементом из неког скупа графова. У Алгоритму \ref{alg:ssabbr} смо показали да је овај поступак неопходан за генерисање групе графова који су структурно слични неком графу. 

У ранијој фази истраживања коришћен је  \textit{VF2} алгоритам за проверу изоморфизма, чија временска комплексност варира између $O(n^2)$ и $O(n!n)$ \cite{skiena}. Овај метод проверава изоморфизам два графа. Да би проверили да ли је неки граф изоморфан са било којим елементом из неког скупа графова, неопходно је итерирати кроз тај скуп и сваки његов елемент понаособ упоредити са испитиванм графом уз помоћ \textit{is\_isomorhic} методa. Овакво решење се показало као врло неефикасно.

Да би се решење убрзало, осмишљен је оригиналан начин за генерисање \textit{GED=1} скупа. Опште позната чињеница у свету алгоритама је да хеш мапе предтављају стрктуру података која омогућава брз начин за претрагу података \cite{skiena}. Стављањем информација о тополошкој структури графа у хеш мапе наш програм би био знатно убрзан. Тачније, уколико је на јединствен начин могуће обележити тополошку структуру неког графа, провера изоморфизма графа са елементима неког скупа графова би се једноставно свела на претрагу хеш мапе. За граф чије се тополошко обележје не налази у хеш табели закључујемо да није изоморфан ни са једним елементом скупа графова. Такав граф можемо да додамо у тај скуп, а самим тим и његово тополошко опбележје у хеш мапу.

Дакле, оригинални приступ решавања проблема генерисања \textit{GED=1} скупа састоји се из проналаска тополошког обележја графа и убрзања провере изоморфизма коришћењем хеш мапи.
Конкретно у нашем случају, било је потребно наћи начин за одређивање тополошког обележја некоренских стабала.


\subsection{Тополошко обележавање коренског стабла}

Као што смо већ поменули, наше истраживање се своди на класе стабала са истим бројем чворова. Познато је да постоје алгоритми који врше тополошко обележавање коренских стабала у линеарном времену \cite{marthe}. Дакле, наш проблем се може решити имплементацијом једног од ових алгоритама и употребом хеш мапа за чување тополошких вредности, под условом да постоји начинн за трансформацију некоренских стабала у коренска. Алгоритам \ref{alg:lbl} приказује како се може извршити тополошко обележавање једног коренског стабла.

\SetKwProg{Fn}{def}{\string:}{}
\begin{algorithm}
\Fn(\tcc*[h]{recursive function}){Label(node)}{
\textit{subtreeLabel} ← []\;
\textit{number←Length(node.children)}\;
\If{number == 0}{
	\textbf{return} 0
}

\textit{children} ← \textit{node.children}\;
\For{ child in children }{
\textit{subtreeLabels.add(Label(child))}
}
\textit{Sort(subtreeLables)}\;

\textbf{return} (\textit{number + ',' + subtreeLabels.joinWith(',')})\;
}
\caption{Тополошко обележавање коренског стабла} 
\label{alg:lbl}
\end{algorithm}


Уочава се да је у алгоритму искорошћен такозвани метод подели-и-освоји који је рекурзивног типа. Слика \ref{fig:lbl} приказује како тече процес обележавања графа. Треба уочити како се (због рекурзивног својства алогоритма) процес изводи од листова ка корену.


\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=120mm]{images/label.png}
\end{center}
\caption{Тополошко обележавање коренског стабла}
\label{fig:lbl}
\end{figure}


Посматрајући алгоритам можемо уочити да се тополошко обележје коренског стабла предтавља као стринг састављен из: броја чворова који су директни потомци корена стабла, и лексикографски сортираних обележја свих подстабала са кореном у чвору који је директан потомак корена тог стабла. Стабло састављено из једног чвора има обележје 0. Сортирањем обележја се занемарује утицај редоследа потомака корена на тополошко обележје стабла, што предствавља кључну ствар код провере изоморфизма. Лако се уочава да алгоритам има линерану комплексност.



\subsection{Трансформација у коренскo стаблo}

У претходном делу је објашњен алгоритам за тополошко обележавање коренског стабла. Овај алгоритам се, међутим, може употребити на некоренским стаблима, што је потребно за израчунавање глаткости индекса \cite{marthe}. Некоренска стабла можемо лако трансформисати у коренска избором одговарајућег чвора за корен стабла. Да би валидно проверавали изоморфизам графова неопходно је наћи начин за одабир јединственог чвора за корен стабла тј. да за два изоморфна стабла увек изаберемо исти чвор као корен. 

На основу претходног објашњења тополошко обележје некоренског стабла се израчунава на следећи начин:

\begin{itemize}
\item Уколико у стаблу постоји један чвор са максималним степенoм, тополошко обележје тог стабла одговара тополошком обележју коренског стабла са кореном у чвору са максималним бројем степена.
\item Нека je $K(u)$ скуп повезаних компоненти графа који настаје када се из стабла уколни неки чвор $u$. Нека је $S$ скуп чворова такав да важи:
\begin{equation}
S = \{u \in V :\;  (\forall K \in K(u): |K| \leq \frac{|V|}{2}) \}
\end{equation}
Уколико за стабло које испитујемо скуп $S$ садржи један елемент, тополошко обележје тог стабла одговара тополошком обележју коренског стабла са кореном у једином елементу скупа $S$.
\item Уколико за стабло које испитујемо, претходно дефнисани скуп $S$ садржи два елемента (што се дешава у појединим случајевима код стабала са парним бројем чворова), тополошко обележје тог стабла одговара лексикографски мањем од два тополошка обележја коренских стабала са коренима у елементима скупа $S$.
\end{itemize}

Да би процес провере изоморфизма имао линеарну комплексност потребно је да претходно описан поступак има линеарну комплексност. Генерисање тополошког обележја стабла и тражење чворова са максималним степеном су процеси са линеарном комплексношћу. Потребно је објаснити како се у линеарном времену генерише скуп $S$. 


Да бисмо генерисали скуп $S$, наше стабло прво претварамо у коренско, произвољним избром чвора који преставља корен. Нека са $w(u)$ обележимо тежину подстабла, односно број елемената у подстаблу испитиваног стабла, са кореном у чвору $u$. Након тога примењујемо Алгоритам \ref{alg:weigh} за проналажење скупа $S$.

Алгоритам \ref{alg:weigh}, дакле, тражи чвор који би при избацивању из стабла поделио стабло на више компоненти од којих ниједна не би имала више од $\frac{n}{2}$ чворова, где је $n$ број чворова стабла. Очигледно је да овај алгоритам има линерану комплексност, тако да је сада могуће имплементирати алгоритам за проверу изоморфности који има линеарну комплексност.



\SetKwProg{Fn}{def}{\string:}{}
\begin{algorithm}[H]
\Fn(\tcc*[h]{recursive function}){Shift(u)}{
\If{$\neg\exists v: (u,v) \in E \wedge w(v)> \frac{n}{2}$ }{
\Return \{u\}\;
}
\ElseIf{$\exists v: (u,v) \in E \wedge w(v) = \frac{n}{2}$}{
\Return \{u,v\}\;
}
\Else{
$v \leftarrow w: (w,u) \in E \wedge w(w) > \frac{n}{2} $\;
$w(u) = w(u) - w(v)$\;
$w(v)= w(u)+w(v)$\;
\Return \textit{Shift(v)}\;
}
}
\caption{Тражење тежинског центра стабла} 
\label{alg:weigh}
\end{algorithm}
\vspace{5mm}

Слика \ref{fig:weigh}. показује како се врши прерачунавање тежина чворова при процесу избора новог корена стабла.

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=150mm]{images/shift.png}
\end{center}
\caption{Тражење тежинског центра стабла}
\label{fig:weigh}
\end{figure}


\chapter*{Закључак}

Циљ овог рада је био опис истраживања глаткости молекулсих структурних дескриптора. 

Дефинисана су два нова појма у хемијској теорији графова(структурна осетљивост и максимални отклон), уз помоћ којих је лакше порценити квалитет хемијског индекса са аспекта глаткости. Такође, осмишљен је оригинални алгоритам за проверу изоморфизма стабала у линеарном времену.

У наставку истраживања је пожељно имплементирати софтвер за рачунање структурне осетљивости и максималног отклона тополошког индекса, базиран на овом раду.
 



\begin{thebibliography}{10}
\bibitem{gutman} {Иван Гутман, Увод у хемијску теорију графова, Крагујевац, 2003}
\bibitem{boris} {Борис Фуртула, On structure-sensitivity of degree-based topological indices, Крагујевац, 2013}
\bibitem{skiena} {Steven Skiena, The Algorithm Design Manual, Springer, 2008}
\bibitem{marthe} {http://perso.ens-lyon.fr/eric.thierry/Graphes2010/marthe-bonamy.pdf, Small Report on Graph and Tree Isomorphism, 2010}
\end{thebibliography}

	
\end{document}


